//class Solution {
//public:
//    void Travel(TreeNode* root, string& str) {
//        if (root == nullptr) {
//            return;
//        }
//        str += to_string(root->val);
//        if (root->left || (root->left == nullptr && root->right != nullptr))
//            str += '(';
//        Travel(root->left, str);
//        if (root->left || (root->left == nullptr && root->right != nullptr))
//            str += ')';
//        if (root->right)
//            str += '(';
//        Travel(root->right, str);
//        if (root->right)
//            str += ')';
//    }
//    string tree2str(TreeNode* root) {
//        string str("");
//        Travel(root, str);
//        return str;
//    }
//};

//class Solution {
//public:
//    vector<vector<int>> levelOrder(TreeNode* root) {
//        vector<vector<int>> v1;
//        queue<TreeNode*> q;
//        if (root) {
//            q.push(root);
//        }
//        while (!q.empty()) {
//            vector<int> v2;
//            for (int i = q.size(); i > 0; i--) {
//                root = q.front();
//                v2.push_back(root->val);
//                if (root->left) {
//                    q.push(root->left);
//                }
//                if (root->right) {
//                    q.push(root->right);
//                }
//                q.pop();
//            }
//            v1.push_back(v2);
//        }
//
//        return v1;
//    }
//};

//class Solution {
//public:
//    vector<vector<int>> levelOrderBottom(TreeNode* root) {
//        vector<vector<int>> v1;
//        queue<TreeNode*> q;
//        if (root) {
//            q.push(root);
//        }
//        while (!q.empty()) {
//            vector<int> v2;
//            for (int i = q.size(); i > 0; i--) {
//                root = q.front();
//                v2.push_back(root->val);
//                if (root->left) {
//                    q.push(root->left);
//                }
//                if (root->right) {
//                    q.push(root->right);
//                }
//                q.pop();
//            }
//            v1.push_back(v2);
//        }
//        reverse(v1.begin(), v1.end());
//        return v1;
//    }
//};

//class Solution {
//public:
//    bool Travel(TreeNode* root, TreeNode* x) {
//        if (root == nullptr) {
//            return false;
//        }
//        if (root == x) {
//            return true;
//        }
//        return Travel(root->left, x) || Travel(root->right, x);
//    }
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        if (root == nullptr) {
//            return nullptr;
//        }
//        if (root == p || root == q) {
//            return root;
//        }
//        bool prootleft = Travel(root->left, p);
//        bool prootright = !prootleft;
//        bool qrootleft = Travel(root->left, q);
//        bool qrootright = !qrootleft;
//        if ((prootleft && qrootright) || (prootright && qrootleft)) {
//            return root;
//        }
//        else if (prootleft && qrootleft) {
//            return lowestCommonAncestor(root->left, p, q);
//        }
//        else
//            return lowestCommonAncestor(root->right, p, q);
//    }
//};